import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: yinsh
 * Date: 2025-02-27
 * Time: 20:12
 */
class Solution {
    Map<String,Integer> map = new HashMap<>();
    static class MapCom implements Comparator<Map.Entry<String,Integer>> {

        @Override
        public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
            if (Objects.equals(o1.getValue(), o2.getValue())) {
                return o1.getKey().compareTo(o2.getKey());
            } else {
                return o2.getValue().compareTo(o1.getValue());
            }
        }
    }

    public List<String> topKFrequent(String[] words, int k) {
        PriorityQueue<Map.Entry<String, Integer>> priorityQueue = new PriorityQueue<>(new MapCom());
        for (int i = 0; i < words.length; i++) {
            int value = map.getOrDefault(words[i],0);
            map.put(words[i],++value);
        }
        List<String> list = new ArrayList<>();
        for (Map.Entry<String,Integer> entry: map.entrySet()) {
            priorityQueue.offer(entry);
            if (priorityQueue.size() > k) {
                priorityQueue.poll();
            }
        }
        List<String> rec = new ArrayList<>();
        while (!priorityQueue.isEmpty()) {
            rec.add(priorityQueue.poll().getKey());
        }
        Collections.reverse(rec);
        return rec;
    }
}
